package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class IsMatchByDPFunc {
    private Map<String,Boolean> map;

    boolean dp(String s,int i,String p,int j){
        if(j==p.length()){
            return i == s.length();
        }
        if(i==s.length()){
            //查看是否能够匹配空串即可
            //如果能够匹配空串,那么就一定是一个字符和*成对出现的
            if((p.length()-j)%2 == 1 ){
                return false;
            }
            for(;j+1<p.length();j+=2){
                if(p.charAt(j+1)!='*'){
                    return false;
                }
            }
            return true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(i);
        stringBuilder.append(",");
        stringBuilder.append(j);
        Boolean res = map.get(stringBuilder.toString());
        //System.out.println(stringBuilder.toString()+","+res);
        if(res != null){
            return res;
        }
        boolean resNow;
        //首先我们来处理匹配的这种情形
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
            if(j<p.length()-1 && p.charAt(j+1) == '*'){
                //通配符匹配0次或者n次
                resNow =  dp(s,i,p,j+2) || dp(s,i+1,p,j);
            }else{
                resNow =  dp(s,i+1,p,j+1);//双指针步进
            }
        }else{
            //不匹配
            if(j<p.length()-1 && p.charAt(j+1) == '*'){
                //就是匹配0次了
                resNow = dp(s,i,p,j+2);//p指针
            }else{
                resNow =  false;
            }
        }
        map.put(stringBuilder.toString(),resNow);
        return resNow;
    }

    public boolean isMatch(String s, String p) {
        map = new HashMap<>();
        return dp(s,0,p,0);
    }

    @Test
    public void test(){
        System.out.println(isMatch("aa","a"));
        System.out.println(isMatch("aa","a*"));
    }
}
